// 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
// 思路，贪心
// 只有一只股票！当前只有买股票或者卖股票的操作,想获得利润至少要两天为一个交易单元。
// 局部最优：收集每天的正利润， 全局最优：求得最大利润

function maxProfit(prices) {
    let ans = 0
    for (let i = 1; i < prices.length; i++) {
        ans += Math.max(0, prices[i] - prices[i-1])        
    }
    return ans
}


// 思路2，动态规划
// 和上一题的区别在于，可以多次买票股票
// 递推公式
// 1. 第i天持有股票的最大金额
//     1. 第i-1天持有股票，`dp[i-1][0]`
//     2. 第i天买入股票，`dp[i-1][1] - price[i]`,这里和上一题不同，因为可以交易多次，第i次买入，之前多次交易可能会有利润
//     3. `dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i])`
// 2. 第i天不持有股票的最大金额
//     1. 第i-1天不持有，`dp[i-1][1]`
//     2. 第i天卖出股票，`dp[i-1][0] + price[i]`
//     3. `dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])`

// 时间复杂度：O(n),空间复杂度：O(n)

function maxProfit2(prices) {
    let dp = new Array(prices.length).fill(0).map(_ => [-Infinity, -Infinity])
    // 这里是买入，所以是负的
    dp[0][0] = -prices[0]
    dp[0][1] = 0
    for (let i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i])
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
    }
    return dp[prices.length - 1][1]
}

// 思路3，动态规划，滚动数组
function maxProfit3(prices) {
    let dp = new Array(2).fill(0).map(_ => [-Infinity, -Infinity])
    dp[0][0] = -prices[0]
    dp[0][1] = 0
    for (let i = 1; i < prices.length; i++) {
        dp[i % 2][0] = Math.max(dp[(i-1) % 2][0], dp[(i-1) % 2][1] - prices[i])        
        dp[i % 2][1] = Math.max(dp[(i-1) % 2][1], dp[(i-1) % 2][0] + prices[i])        
    }
    return dp[(prices.length - 1) % 2][1]
}

console.log(maxProfit([7,1,5,3,6,4]))
console.log(maxProfit2([7,1,5,3,6,4]))
console.log(maxProfit3([7,1,5,3,6,4]))